package Test1;
/**
 * @Date 2020/03/26
 * @author 王光浩
 * @Thinking 先使用一个数组记录所有字母的个数，然后找出最大次数的字母，判断这个字符串是否符合要求，如果符合
 * @         要求，按照数组中字符出现的个数，重新创建一个字符串，然后将字符依次存入字符串中，然后使用双指针
 * @         将最后一个字符和第二字符进行交换，然后后指针前移两个，前指针后移两个。
 * @         难点不在于字符串是否符合要求，而在于构建当字符串符合要求后，构造出一个符合要求的字符串。
 */
public class QuestionTwo2 {
	public String reorganizeString(String S) {
		char[] countNumb=new char[26];
		//统计字符个数时间复杂度O（n）
		for(int i=0;i<S.length();i++)
			countNumb[S.charAt(i)-97]++;
		//判断是否符合要求
		int max=-1;
		for(int i=0;i<26;i++)
			max=countNumb[i]>max?countNumb[i]:max;
		if(max>(S.length()+1)/2)return "";
		//找出一个符合要求的字符串
		StringBuilder ret=new StringBuilder();
			//按字母出现次数从大到小，将字母依次放入ret中（时间复杂度O（n））
		boolean flag=true;
		while(flag) {
			int maxIndex=0;
			for(int j=0;j<26;j++)
				maxIndex=countNumb[j]>countNumb[maxIndex]?j:maxIndex;
			if(countNumb[maxIndex]==0)flag=false;
			while(countNumb[maxIndex]>0) {
					ret.append((char)(maxIndex+97));
					countNumb[maxIndex]--;
			}
		}
			//将字符依次放入数组中（让字符间隔的方式依次放入数组中）
		char[] res=new char[S.length()];
		int index=0;
		for(int i=0;i<S.length();i+=2) {
			res[i]=ret.charAt(index++);
		}
		for(int i=1;i<S.length();i+=2)
			res[i]=ret.charAt(index++);
		return new String(res);
	}
}
